package com.mlamp.二叉树;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 二叉树的中序遍历 {

    private List<Integer> res = new ArrayList<>();

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = null;
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);
        root.right.right = null;

//        二叉树的中序遍历 instance = new 二叉树的中序遍历();
//        List<Integer> integers = instance.inorderTraversal(root);
//        System.out.println(Arrays.toString(integers.toArray()));
//
//        instance.reset();
//        root = null;
//        System.out.println(Arrays.toString(instance.inorderTraversal(root).toArray()));
//
//
//        instance.reset();
//        root = new TreeNode(1);
//        System.out.println(Arrays.toString(instance.inorderTraversal(root).toArray()));


        二叉树的中序遍历 instance = new 二叉树的中序遍历();

        /**
         *
         */
        System.out.println("前序遍历二叉树");
        instance.preordertraverse(root);

        System.out.println("-----------------");

        instance.preOrderTraversalA(root);
        System.out.println("-----------------");

        System.out.println();
        System.out.println("中序遍历二叉树");
        instance.inordertraverse(root);
        System.out.println("------------------");
        instance.inorderTraversalA(root);

        System.out.println("-------------------");
        System.out.println();
        System.out.println("后序遍历二叉树");
        instance.postordertraverse(root);
        System.out.println("---------------------");
        instance.postOrderTraversal(root);
        System.out.println("---------------------");


    }


    public void reset() {
        res.clear();
    }


    public void inorderTraversal2(TreeNode root, List<Integer> path) {
        if (root == null) return;
        if (root.left != null)
            inorderTraversal(root.left);
        path.add(root.val);
        if (root.right != null)
            inorderTraversal(root.right);
    }


    public void preOrderTraversalA(TreeNode root){
        if (root == null) {
            System.out.print("None ");
            return;
        }
        System.out.print(root.val + " ");
        preOrderTraversalA(root.left);
        preOrderTraversalA(root.right);
    }

    public void inorderTraversalA(TreeNode root) {
        if (root == null) {
            System.out.print("None ");
            return;
        }
        inorderTraversalA(root.left);
        System.out.print(root.val + " ");
        inorderTraversalA(root.right);
    }


    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return res;
            //ignore
        }
        if (root.left != null) inorderTraversal(root.left);
        res.add(root.val);
        if (root.right != null) inorderTraversal(root.right);
        return res;
    }


    /**
     * 二叉树的前序遍历
     */

    public void preordertraverse(TreeNode root) {
        if (root == null) {
            System.out.print("none ");
            return;
        }
        //前序
        if (root != null) {
            System.out.print(root.val + " ");
        }
        preordertraverse(root.left);
        preordertraverse(root.right);
    }

    /**
     * 二叉树的中序遍历
     */

    public void inordertraverse(TreeNode root) {
        //前序
        if (root == null) {
            System.out.print("none ");
            return;
        }
        inordertraverse(root.left);
        if (root != null) {
            System.out.print(root.val + " ");
        }

        inordertraverse(root.right);
    }



    public void postOrderTraversal(TreeNode root){
        if(root == null) {
            System.out.print("None ");
            return;
        }
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.print(root.val + " ");
    }




    /**
     * 二叉树的后序遍历
     */
    public void postordertraverse(TreeNode root) {
        if (root == null) {
            System.out.print("none ");
            return;
        }
        postordertraverse(root.left);
        postordertraverse(root.right);
        if (root != null) {
            System.out.print(root.val + " ");
        }
    }

    public static final class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}



